經典貪心問題

找零問題

店員在收錢時，常常會希望可以拿到以最少紙鈔、硬幣組成的現金

那要怎麼才能 n 元以最少的紙鈔、硬幣組成呢?

新台幣常用的紙鈔、硬幣有以下幾種：

• 1元
• 5元
• 10元
• 50元
• 100元
• 500元
• 1000元

那以下是幾個最少紙鈔、硬幣找零的例子：

552 = 500*1 + 50*1 + 1*2
1246 = 1000*1 + 100*2 + 10*4 + 5*1 + 1*1
10000 = 1000*10

那該怎麼設計我們的貪心演算法呢？

其實對照上面例子，可以發現用面額較大的紙鈔或硬幣，可以減少全部紙鈔和硬幣的數量。

因此優先換面額較大的紙鈔或硬幣，換完才換較小的。

constexpr int money[7] = {1000, 500, 100, 50, 10, 5, 1};

vector<pair<int, int>> change(int n) {
    vector<pair<int, int>> res;
    for (int i = 0; i < 7; ++i) {
        if (n >= money[i]) {
            res.emplace_back(money[i], n / money[i]);
            n %= money[i];
        }
    }
    return res;
}

如果寫成程式就是上面的樣子

延伸思考：如果新台幣加入一種新硬幣 23 元，我們貪心演算法還會成立嗎?